// nikonova julia

#include <map>
using std::map;
using std::pair;
using std::make_pair; 

template <typename Name>

class BiGraph {
public:
	class Edge;
	class Vertex;
	BiGraph() {m_edges_count=0;};
	~BiGraph() { clear();};
	size_t vertices_count() const {return m_vertices.size();};
	size_t edge_count() const { return m_edges_count; }
	Vertex* find_or_create_vertex(const Name &v){
        if (m_vertices.find(v)==m_vertices.end()){
            Vertex* new_vertex = new Vertex(v);
            m_vertices.insert(make_pair(v, new_vertex));
            return new_vertex;
        }
        return m_vertices[v];
    }
	double weight(Name start, Name end)
	{
		if (m_vertices.find(start)==m_vertices.end() || m_vertices.find(end)==m_vertices.end())
		{ 
			return numeric_limits<double>::max();
		}
		

		Vertex* start_vertex = find_or_create_vertex(start);
        Vertex* end_vertex = find_or_create_vertex(end);
        
        map<Vertex*, Edge*>::iterator existing_edge=start_vertex->m_out_edges.find(end_vertex);
        
        if ( existing_edge==start_vertex->m_out_edges.end())
		{ 
			return numeric_limits<double>::max(); 
		}
		return existing_edge->second->get_weight();
	}

	template <typename T, typename U>
    class Iterator_Wrapper{
      public:   
        Iterator_Wrapper(T itr) : m_itr(itr) {};
        Iterator_Wrapper& operator++() { m_itr++; return *this;};
        Iterator_Wrapper& operator--() { m_itr--; return *this;};
        Iterator_Wrapper operator++(int) { Iterator_Wrapper old_value(m_itr); m_itr++; return old_value;};
        Iterator_Wrapper operator--(int) { Iterator_Wrapper old_value(m_itr); m_itr--; return old_value;};
        bool operator==(const Iterator_Wrapper& itr_w) const { return (m_itr==itr_w.m_itr);};
        bool operator!=(const Iterator_Wrapper& itr_w) const { return (m_itr!=itr_w.m_itr);};
        U& operator*() { return *(m_itr->second); };
        U* operator->() { return m_itr->second; };
        Iterator_Wrapper& operator=(const Iterator_Wrapper& itr_w) {m_itr=itr_w.m_itr; return *this;};
      private:
        T  m_itr;
    };

	typedef typename map<Name, Vertex*>::iterator n2v_itr;
	typedef Iterator_Wrapper<n2v_itr, Vertex> vertex_iterator;
	typedef pair<vertex_iterator, vertex_iterator> vertices_range;

	typedef typename map<Vertex*, Edge*>::iterator v2e_itr;
	typedef Iterator_Wrapper<v2e_itr, Edge> in_edge_iterator;
	typedef Iterator_Wrapper<v2e_itr, Edge> out_edge_iterator;
    
	class Edge
	{
		public:
			Edge( Vertex* start, Vertex* end, double weight) : m_start(start), m_end(end), m_weight(weight) {};
			pair<Name, Name> get_name() {return make_pair(m_start->get_name(), m_end->get_name());};
			double get_weight() const {return m_weight;};
		private:
			Vertex* m_start;
			Vertex* m_end;
			double m_weight;
	};
	class Vertex
	{
	public:
		Vertex (const Name& name) : m_name(name) {}; 
		Name get_name() const { return m_name;};
		pair<in_edge_iterator, in_edge_iterator> in_edge() { 
			return make_pair(in_edge_iterator(m_in_edges.begin()), in_edge_iterator(m_in_edges.end())); 
		}

		pair<out_edge_iterator, out_edge_iterator> out_edge() { 
			return make_pair(out_edge_iterator(m_out_edges.begin()), out_edge_iterator(m_out_edges.end())); 
		}
	private:
		Name m_name;
		map<Vertex*, Edge*> m_out_edges;
		map<Vertex*, Edge*> m_in_edges;
		
		friend class BiGraph;
	};

	vertices_range  vertices()
	{
		return make_pair(vertex_iterator(m_vertices.begin()), vertex_iterator(m_vertices.end()));
	}

	vertex_iterator begin() 
	{ 
		return vertex_iterator(m_vertices.begin()); 
	}

	vertex_iterator end() 
	{ 
		return vertex_iterator(m_vertices.end()); 
	}
    

	bool add_vertex(const Name& v)
	{
		if (m_vertices.find(v)!=m_vertices.end())
		{
			return false;
		}

		m_vertices.insert(make_pair(v, new Vertex(v)));
		return true;
	}

	Edge* add_edge(const Name & start,const Name & end, double weight){
        if (start==end) {return 0;}
        
        Vertex* start_vertex = find_or_create_vertex(start);
        Vertex* end_vertex = find_or_create_vertex(end);
        
        map<Vertex*, Edge*>::iterator existing_edge=start_vertex->m_out_edges.find(end_vertex);
        
        if ( existing_edge!=start_vertex->m_out_edges.end()){ return existing_edge->second; }
        Edge* new_edge = new Edge(start_vertex, end_vertex, weight);
        start_vertex->m_out_edges.insert(make_pair(end_vertex, new_edge));
        end_vertex->m_in_edges.insert(make_pair(start_vertex, new_edge));
        
        ++m_edges_count;
        return new_edge;
    }

	bool delete_edge(const Name & start, const Name & end)
	{
		if (m_vertices.find(start)==m_vertices.end() || m_vertices.find(end)==m_vertices.end()) { 
			return false; 
		}
    
        Vertex* start_vertex = m_vertices[start];
		Vertex* end_vertex = m_vertices[end];
		if ( start_vertex->m_out_edges.find(end_vertex)==start_vertex->m_out_edges.end()) { 
			return false;
		}

		start_vertex->m_out_edges.erase(end_vertex);
		delete end_vertex->m_in_edges[start_vertex];
		end_vertex-> m_in_edges.erase(start_vertex);
        m_edges_count--;
		return true;
	}	

	void clear()
	{
		m_edges_count=0;
		for (map<Name, Vertex*>::iterator itr_vertex = m_vertices.begin(); itr_vertex != m_vertices.end(); itr_vertex++)
		{
			for (map<Vertex*, Edge*>::iterator itr_edge=itr_vertex->second->m_out_edges.begin(); itr_edge!=itr_vertex->second->m_out_edges.end(); itr_edge++)
			{
				delete itr_edge->second;
			}

			delete itr_vertex->second;
		}
		

		m_vertices.clear();
	}

	void show()
	{
		vertices_range vertices=this->vertices();
		for (vertex_iterator itr_v=vertices.first; itr_v!=vertices.second; itr_v++) 
		{
			pair<out_edge_iterator, out_edge_iterator> edges=itr_v->out_edge();
			for (out_edge_iterator itr_e=edges.first; itr_e!=edges.second; itr_e++){
				cout<<(itr_e->get_name()).first<<" "<<(itr_e->get_name()).second<<" "<<(itr_e->get_weight())<<endl;
			}
		} 
	}


	

private:
	map<Name, Vertex*> m_vertices;
	size_t m_edges_count;
	
	

};

